package A一周刷爆LeetCode.A基础班.F二叉树;

import java.util.LinkedList;

/**
 * @author wei.zhao
 * @description: 折纸问题
 * @date 2022年03月03日 17:11
 */
public class Code13_PaperFolding {

    public static void main(String[] args) {
        printAllFolds01(4);
        System.out.println();
        printAllFolds02(4);
    }

    /**
     * 先构建二叉树，再中序遍历
     */
    public static void printAllFolds01(int N) {
        // 构建二叉树，头节点是凹，左节点凹，右节点凸
        Node head = new Node(0);
        LinkedList<Node> nodes1 = new LinkedList<>();
        nodes1.add(head);
        for (int i = 1; i < N; i++) {
            LinkedList<Node> nodes2 = new LinkedList<>();
            while (!nodes1.isEmpty()) {
                Node node = nodes1.pop();
                Node node1 = new Node(0);
                Node node2 = new Node(1);
                node.left = node1;
                node.right = node2;
                nodes2.add(node1);
                nodes2.add(node2);
            }
            nodes1.addAll(nodes2);
        }
        //打印，中序遍历
        midTraversal(head);
    }

    private static void midTraversal(Node head) {
        if (head == null) {
            return;
        }
        midTraversal(head.left);
        System.out.print(head.value == 0 ? "凹" + " " : "凸" + " ");
        midTraversal(head.right);
    }

    /**
     * 巧妙解法
     */
    public static void printAllFolds02(int N) {
        process(N, 1, "凹 ");
    }

    private static void process(int max, int cur, String s) {
        if (cur > max) {
            return;
        }
        process(max, cur + 1, "凹 ");
        System.out.print(s);
        process(max, cur + 1, "凸 ");
    }

}